064. Minimum Path Sum[M]

题目

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

思路

DP

这应该是很容易想到的，因为每次只能往下或右走，所以对于每个格，就两种可能：

  • 从上面走下来

  • 从左边走过来
    那么很容易写出表达式：dp(i,j) = min(dp(i-1,j) , dp(i,j-1)) + path(i,j)
    然后要做一个处理，就是对于第0行，和第0列只能从左边或上面走。这样判断很麻烦，其实有一个很简单的办法：
    增加一行和一列，让这一行和这一列都为一个很大的值，这样，不管是第0行还是0列，都可以用统一的算法。
    （这里有个小注意点，就是我对minpath[0][1]赋值为0，这是为了更改原来minpath[0][0]位置的值）

    1. public class Solution {
    2.   public int minPathSum(int[][] grid) {
    3.       int m = grid.length;
    4.       if(0 == m)
    5.           return 0;
    6.       int n = grid[0].length;
    7.       int [][] minpath = new int[m+1][n+1];
    8.       //init 0th row and 0th column to Max
    9.       for(int i = 0;i <= m;i ++)
    10.           minpath[i][0] = Integer.MAX_VALUE;
    11.       for(int j = 0;j <= n;j ++)
    12.           minpath[0][j] = Integer.MAX_VALUE;
    14.       minpath[0][1] = 0;
    16.       for(int i = 1;i <= m;i ++)
    17.           for(int j = 1;j <= n;j++)
    18.                   minpath[i][j] = Math.min(minpath[i-1][j],minpath[i][j-1]) + grid[i-1][j-1];
    20.       return minpath[m][n];
    22.   }
    23. }

　一维数组

当然，上面的算法还可以改进，就是把二维数组换成一维数组，因为我们实际运行的时候发现，我们每次计算只和当前行的grid和之前行的minpath有关。
这个一维数组一直会更新，而更新条件就是 : dp[j] = min(dp(j),dp(j-1)) + grid(i,j)
这里同样为了避免第0列出问题（j-1越界），加入了1格，实际j从1开始 

  1. public class Solution {
  2.     public int minPathSum(int[][] grid) {
  3.         int m = grid.length;
  4.         if(0 == m)
  5.             return 0;
  6.         int n = grid[0].length;
  7.         int [] minpath = new int[n+1];
  8.         for(int i = 0;i <= n;i ++)
  9.             minpath[i] = Integer.MAX_VALUE;
  11.         minpath[1] = 0;
  13.         for(int i = 0;i < m;i ++)
  14.             for(int j = 1;j <= n;j++)
  15.                 minpath[j] = Math.min(minpath[j-1],minpath[j]) + grid[i][j-1];
  17.         return minpath[n];
  19.     }
  20. }